/*
 * Copyright (c) 2012, Google Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "flutter/sky/engine/platform/graphics/RegionTracker.h"

#include "flutter/sky/engine/platform/graphics/GraphicsContext.h"
#include "third_party/skia/include/core/SkColorFilter.h"
#include "third_party/skia/include/core/SkShader.h"

namespace blink {

RegionTracker::RegionTracker()
    : m_opaqueRect(SkRect::MakeEmpty()), m_trackedRegionType(Opaque) {}

void RegionTracker::reset() {
  ASSERT(m_canvasLayerStack.isEmpty());
  m_opaqueRect = SkRect::MakeEmpty();
}

IntRect RegionTracker::asRect() const {
  // Returns the largest enclosed rect.
  // TODO: actually, this logic looks like its returning the smallest.
  //       to return largest, shouldn't we take floor of left/top
  //       and the ceil of right/bottom?
  int left = SkScalarCeilToInt(m_opaqueRect.fLeft);
  int top = SkScalarCeilToInt(m_opaqueRect.fTop);
  int right = SkScalarFloorToInt(m_opaqueRect.fRight);
  int bottom = SkScalarFloorToInt(m_opaqueRect.fBottom);
  return IntRect(left, top, right - left, bottom - top);
}

// Returns true if the xfermode will force the dst to be opaque, regardless of
// the current dst.
static inline bool xfermodeIsOpaque(const SkPaint& paint, bool srcIsOpaque) {
  if (!srcIsOpaque)
    return false;

  switch (paint.getBlendMode()) {
    case SkBlendMode::kSrc:      // source
    case SkBlendMode::kSrcOver:  // source + dest - source*dest
    case SkBlendMode::kDstOver:  // source + dest - source*dest
    case SkBlendMode::kDstATop:  // source
    case SkBlendMode::kPlus:     // source+dest
    default:                     // the rest are all source + dest - source*dest
      return true;
    case SkBlendMode::kClear:    // 0
    case SkBlendMode::kDst:      // dest
    case SkBlendMode::kSrcIn:    // source * dest
    case SkBlendMode::kDstIn:    // dest * source
    case SkBlendMode::kSrcOut:   // source * (1-dest)
    case SkBlendMode::kDstOut:   // dest * (1-source)
    case SkBlendMode::kSrcATop:  // dest
    case SkBlendMode::kXor:      // source + dest - 2*(source*dest)
      return false;
  }
}

static inline bool xfermodeIsOverwrite(const SkPaint& paint) {
  switch (paint.getBlendMode()) {
    case SkBlendMode::kSrc:
    case SkBlendMode::kClear:
      return true;
    default:
      return false;
  }
}

// Returns true if the xfermode will keep the dst opaque, assuming the dst is
// already opaque.
static inline bool xfermodePreservesOpaque(const SkPaint& paint,
                                           bool srcIsOpaque) {
  switch (paint.getBlendMode()) {
    case SkBlendMode::kDst:      // dest
    case SkBlendMode::kSrcOver:  // source + dest - source*dest
    case SkBlendMode::kDstOver:  // source + dest - source*dest
    case SkBlendMode::kSrcATop:  // dest
    case SkBlendMode::kPlus:     // source+dest
    default:                     // the rest are all source + dest - source*dest
      return true;
    case SkBlendMode::kClear:   // 0
    case SkBlendMode::kSrcOut:  // source * (1-dest)
    case SkBlendMode::kDstOut:  // dest * (1-source)
    case SkBlendMode::kXor:     // source + dest - 2*(source*dest)
      return false;
    case SkBlendMode::kSrc:      // source
    case SkBlendMode::kSrcIn:    // source * dest
    case SkBlendMode::kDstIn:    // dest * source
    case SkBlendMode::kDstATop:  // source
      return srcIsOpaque;
  }
}

// Returns true if all pixels painted will be opaque.
static inline bool paintIsOpaque(const SkPaint& paint,
                                 RegionTracker::DrawType drawType,
                                 const SkBitmap* bitmap) {
  if (paint.getAlpha() < 0xFF)
    return false;
  bool checkFillOnly = drawType != RegionTracker::FillOrStroke;
  if (!checkFillOnly && paint.getStyle() != SkPaint::kFill_Style &&
      paint.isAntiAlias())
    return false;
  SkShader* shader = paint.getShader();
  if (shader && !shader->isOpaque())
    return false;
  if (bitmap && !bitmap->isOpaque())
    return false;
  if (paint.getLooper())
    return false;
  if (paint.getImageFilter())
    return false;
  if (paint.getMaskFilter())
    return false;
  SkColorFilter* colorFilter = paint.getColorFilter();
  if (colorFilter &&
      !(colorFilter->getFlags() & SkColorFilter::kAlphaUnchanged_Flag))
    return false;
  return true;
}

// Returns true if there is a rectangular clip, with the result in
// |deviceClipRect|.
static inline bool getDeviceClipAsRect(const GraphicsContext* context,
                                       SkRect& deviceClipRect) {
  // Get the current clip in device coordinate space.
  if (!context->canvas()->isClipRect()) {
    deviceClipRect.setEmpty();
    return false;
  }

  SkIRect deviceClipIRect;
  if (context->canvas()->getDeviceClipBounds(&deviceClipIRect))
    deviceClipRect.set(deviceClipIRect);
  else
    deviceClipRect.setEmpty();

  return true;
}

void RegionTracker::pushCanvasLayer(const SkPaint* paint) {
  CanvasLayerState state;
  if (paint)
    state.paint = *paint;
  m_canvasLayerStack.append(state);
}

void RegionTracker::popCanvasLayer(const GraphicsContext* context) {
  ASSERT(!m_canvasLayerStack.isEmpty());
  if (m_canvasLayerStack.isEmpty())
    return;

  const CanvasLayerState& canvasLayer = m_canvasLayerStack.last();
  SkRect layerOpaqueRect = canvasLayer.opaqueRect;
  SkPaint layerPaint = canvasLayer.paint;

  // Apply the image mask.
  if (canvasLayer.hasImageMask &&
      !layerOpaqueRect.intersect(canvasLayer.imageOpaqueRect))
    layerOpaqueRect.setEmpty();

  m_canvasLayerStack.removeLast();

  applyOpaqueRegionFromLayer(context, layerOpaqueRect, layerPaint);
}

void RegionTracker::setImageMask(const SkRect& imageOpaqueRect) {
  ASSERT(!m_canvasLayerStack.isEmpty());
  m_canvasLayerStack.last().hasImageMask = true;
  m_canvasLayerStack.last().imageOpaqueRect = imageOpaqueRect;
}

void RegionTracker::didDrawRect(const GraphicsContext* context,
                                const SkRect& fillRect,
                                const SkPaint& paint,
                                const SkBitmap* sourceBitmap) {
  // Any stroking may put alpha in pixels even if the filling part does not.
  if (paint.getStyle() != SkPaint::kFill_Style) {
    bool fillsBounds = false;

    if (!paint.canComputeFastBounds()) {
      didDrawUnbounded(context, paint, FillOrStroke);
    } else {
      SkRect strokeRect;
      strokeRect = paint.computeFastBounds(fillRect, &strokeRect);
      didDraw(context, strokeRect, paint, sourceBitmap, fillsBounds,
              FillOrStroke);
    }
  }

  bool fillsBounds = paint.getStyle() != SkPaint::kStroke_Style;
  didDraw(context, fillRect, paint, sourceBitmap, fillsBounds, FillOnly);
}

void RegionTracker::didDrawPath(const GraphicsContext* context,
                                const SkPath& path,
                                const SkPaint& paint) {
  SkRect rect;
  if (path.isRect(&rect)) {
    didDrawRect(context, rect, paint, 0);
    return;
  }

  bool fillsBounds = false;

  if (!paint.canComputeFastBounds()) {
    didDrawUnbounded(context, paint, FillOrStroke);
  } else {
    rect = paint.computeFastBounds(path.getBounds(), &rect);
    didDraw(context, rect, paint, 0, fillsBounds, FillOrStroke);
  }
}

void RegionTracker::didDrawPoints(const GraphicsContext* context,
                                  SkCanvas::PointMode mode,
                                  int numPoints,
                                  const SkPoint points[],
                                  const SkPaint& paint) {
  if (!numPoints)
    return;

  SkRect rect;
  rect.fLeft = points[0].fX;
  rect.fRight = points[0].fX + 1;
  rect.fTop = points[0].fY;
  rect.fBottom = points[0].fY + 1;

  for (int i = 1; i < numPoints; ++i) {
    rect.fLeft = std::min(rect.fLeft, points[i].fX);
    rect.fRight = std::max(rect.fRight, points[i].fX + 1);
    rect.fTop = std::min(rect.fTop, points[i].fY);
    rect.fBottom = std::max(rect.fBottom, points[i].fY + 1);
  }

  bool fillsBounds = false;

  if (!paint.canComputeFastBounds()) {
    didDrawUnbounded(context, paint, FillOrStroke);
  } else {
    rect = paint.computeFastBounds(rect, &rect);
    didDraw(context, rect, paint, 0, fillsBounds, FillOrStroke);
  }
}

void RegionTracker::didDrawBounded(const GraphicsContext* context,
                                   const SkRect& bounds,
                                   const SkPaint& paint) {
  bool fillsBounds = false;

  if (!paint.canComputeFastBounds()) {
    didDrawUnbounded(context, paint, FillOrStroke);
  } else {
    SkRect rect;
    rect = paint.computeFastBounds(bounds, &rect);
    didDraw(context, rect, paint, 0, fillsBounds, FillOrStroke);
  }
}

void RegionTracker::didDraw(const GraphicsContext* context,
                            const SkRect& rect,
                            const SkPaint& paint,
                            const SkBitmap* sourceBitmap,
                            bool fillsBounds,
                            DrawType drawType) {
  SkRect targetRect = rect;

  // Apply the transform to device coordinate space.
  SkMatrix canvasTransform = context->canvas()->getTotalMatrix();
  if (!canvasTransform.mapRect(&targetRect))
    fillsBounds = false;

  // Apply the current clip.
  SkRect deviceClipRect;
  if (!getDeviceClipAsRect(context, deviceClipRect))
    fillsBounds = false;
  else if (!targetRect.intersect(deviceClipRect))
    return;

  if (m_trackedRegionType == Overwrite && fillsBounds &&
      xfermodeIsOverwrite(paint)) {
    markRectAsOpaque(targetRect);
    return;
  }

  bool drawsOpaque = paintIsOpaque(paint, drawType, sourceBitmap);
  bool xfersOpaque = xfermodeIsOpaque(paint, drawsOpaque);

  if (fillsBounds && xfersOpaque) {
    markRectAsOpaque(targetRect);
  } else if (m_trackedRegionType == Opaque &&
             !xfermodePreservesOpaque(paint, drawsOpaque)) {
    markRectAsNonOpaque(targetRect);
  }
}

void RegionTracker::didDrawUnbounded(const GraphicsContext* context,
                                     const SkPaint& paint,
                                     DrawType drawType) {
  bool drawsOpaque = paintIsOpaque(paint, drawType, 0);
  bool preservesOpaque = xfermodePreservesOpaque(paint, drawsOpaque);

  if (preservesOpaque)
    return;

  SkRect deviceClipRect;
  getDeviceClipAsRect(context, deviceClipRect);
  markRectAsNonOpaque(deviceClipRect);
}

void RegionTracker::applyOpaqueRegionFromLayer(const GraphicsContext* context,
                                               const SkRect& layerOpaqueRect,
                                               const SkPaint& paint) {
  SkRect deviceClipRect;
  bool deviceClipIsARect = getDeviceClipAsRect(context, deviceClipRect);

  if (deviceClipIsARect && deviceClipRect.isEmpty())
    return;

  SkRect sourceOpaqueRect = layerOpaqueRect;
  // Save the opaque area in the destination, so we can preserve the parts of it
  // under the source opaque area if possible.
  SkRect destinationOpaqueRect = currentTrackingOpaqueRect();

  bool outsideSourceOpaqueRectPreservesOpaque =
      xfermodePreservesOpaque(paint, false);
  if (!outsideSourceOpaqueRectPreservesOpaque) {
    if (!deviceClipIsARect) {
      markAllAsNonOpaque();
      return;
    }
    markRectAsNonOpaque(deviceClipRect);
  }

  if (!deviceClipIsARect)
    return;
  if (!sourceOpaqueRect.intersect(deviceClipRect))
    return;

  bool sourceOpaqueRectDrawsOpaque = paintIsOpaque(paint, FillOnly, 0);
  bool sourceOpaqueRectXfersOpaque =
      xfermodeIsOpaque(paint, sourceOpaqueRectDrawsOpaque);
  bool sourceOpaqueRectPreservesOpaque =
      xfermodePreservesOpaque(paint, sourceOpaqueRectDrawsOpaque);

  // If the layer's opaque area is being drawn opaque in the layer below, then
  // mark it opaque. Otherwise, if it preserves opaque then keep the
  // intersection of the two.
  if (sourceOpaqueRectXfersOpaque)
    markRectAsOpaque(sourceOpaqueRect);
  else if (sourceOpaqueRectPreservesOpaque &&
           sourceOpaqueRect.intersect(destinationOpaqueRect))
    markRectAsOpaque(sourceOpaqueRect);
}

void RegionTracker::markRectAsOpaque(const SkRect& rect) {
  // We want to keep track of an opaque region but bound its complexity at a
  // constant size. We keep track of the largest rectangle seen by area. If we
  // can add the new rect to this rectangle then we do that, as that is the
  // cheapest way to increase the area returned without increasing the
  // complexity.

  SkRect& opaqueRect = currentTrackingOpaqueRect();

  if (rect.isEmpty())
    return;
  if (opaqueRect.contains(rect))
    return;
  if (rect.contains(opaqueRect)) {
    opaqueRect = rect;
    return;
  }

  if (rect.fTop <= opaqueRect.fTop && rect.fBottom >= opaqueRect.fBottom) {
    if (rect.fLeft < opaqueRect.fLeft && rect.fRight >= opaqueRect.fLeft)
      opaqueRect.fLeft = rect.fLeft;
    if (rect.fRight > opaqueRect.fRight && rect.fLeft <= opaqueRect.fRight)
      opaqueRect.fRight = rect.fRight;
  } else if (rect.fLeft <= opaqueRect.fLeft &&
             rect.fRight >= opaqueRect.fRight) {
    if (rect.fTop < opaqueRect.fTop && rect.fBottom >= opaqueRect.fTop)
      opaqueRect.fTop = rect.fTop;
    if (rect.fBottom > opaqueRect.fBottom && rect.fTop <= opaqueRect.fBottom)
      opaqueRect.fBottom = rect.fBottom;
  }

  long opaqueArea = (long)opaqueRect.width() * (long)opaqueRect.height();
  long area = (long)rect.width() * (long)rect.height();
  if (area > opaqueArea)
    opaqueRect = rect;
}

void RegionTracker::markRectAsNonOpaque(const SkRect& rect) {
  // We want to keep as much of the current opaque rectangle as we can, so find
  // the one largest rectangle inside m_opaqueRect that does not intersect with
  // |rect|.

  SkRect& opaqueRect = currentTrackingOpaqueRect();

  if (!SkRect::Intersects(rect, opaqueRect))
    return;
  if (rect.contains(opaqueRect)) {
    markAllAsNonOpaque();
    return;
  }

  int deltaLeft = rect.fLeft - opaqueRect.fLeft;
  int deltaRight = opaqueRect.fRight - rect.fRight;
  int deltaTop = rect.fTop - opaqueRect.fTop;
  int deltaBottom = opaqueRect.fBottom - rect.fBottom;

  // horizontal is the larger of the two rectangles to the left or to the right
  // of |rect| and inside opaqueRect. vertical is the larger of the two
  // rectangles above or below |rect| and inside opaqueRect.
  SkRect horizontal = opaqueRect;
  if (deltaTop > deltaBottom)
    horizontal.fBottom = rect.fTop;
  else
    horizontal.fTop = rect.fBottom;
  SkRect vertical = opaqueRect;
  if (deltaLeft > deltaRight)
    vertical.fRight = rect.fLeft;
  else
    vertical.fLeft = rect.fRight;

  if ((long)horizontal.width() * (long)horizontal.height() >
      (long)vertical.width() * (long)vertical.height())
    opaqueRect = horizontal;
  else
    opaqueRect = vertical;
}

void RegionTracker::markAllAsNonOpaque() {
  SkRect& opaqueRect = currentTrackingOpaqueRect();
  opaqueRect.setEmpty();
}

SkRect& RegionTracker::currentTrackingOpaqueRect() {
  // If we are drawing into a canvas layer, then track the opaque rect in that
  // layer.
  return m_canvasLayerStack.isEmpty() ? m_opaqueRect
                                      : m_canvasLayerStack.last().opaqueRect;
}

}  // namespace blink
